package leetcode.year2021.month10;

/**
 * 75. 颜色分类
 */
public class _23_01SortColors75 {
  public void sortColors(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    int prev = 0;

    while (prev <= right){
      if (nums[prev] == 0) {
        swap(nums, left, prev);
        left++;
        if (prev < left){
          prev = left;
        }
      } else if (nums[prev] == 2){
        swap(nums, right, prev);
        right--;
      } else {
        prev++;
      }
    }
  }

  public static void swap(int[] nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }


  /**
   * 75. 颜色分类
   * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
   *
   * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
   *
   *
   *
   * 示例 1：
   *
   * 输入：nums = [2,0,2,1,1,0]
   * 输出：[0,0,1,1,2,2]
   * 示例 2：
   *
   * 输入：nums = [2,0,1]
   * 输出：[0,1,2]
   * 示例 3：
   *
   * 输入：nums = [0]
   * 输出：[0]
   * 示例 4：
   *
   * 输入：nums = [1]
   * 输出：[1]
   *
   *
   * 提示：
   *
   * n == nums.length
   * 1 <= n <= 300
   * nums[i] 为 0、1 或 2
   */
}
